package medium;

import java.util.ArrayList;
import java.util.List;

/*
113. 路径总和 II
解题思路：dfs
 */
public class LeeCode113 {

  public static void main(String[] args) {

  }

  List<List<Integer>> res = new ArrayList<>();
  List<Integer> list = new ArrayList<>();
  public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    dfs(root,0,targetSum);
    return res;
  }

  public void dfs(TreeNode root,int num,int sum){
    if (root == null){
      return ;
    }
    num = num + root.val;
    list.add(root.val);
    if (root.left == null && root. right == null && num == sum){
      res.add(new ArrayList<>(list));
    }
    dfs(root.left,num,sum);
    dfs(root.right,num,sum);
    list.remove(list.size() - 1);
  }

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
